子集树问题——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

一、全排列 II（LeetCode 47）

问题描述：

• 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列
• 提示：
  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10
• 示例 1：
  • 输入：nums = [1,1,2]
  • 输出：[ [1,1,2], [1,2,1], [2,1,1] ]
• 示例 2：
  • 输入：nums = [1,2,3]
  • 输出：[ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]

算法解析：

1. 先对数组排序，让相同元素相邻，方便后续去重判断
2. 使用回溯法遍历所有可能的排列
3. 去重规则：如果当前元素和前一个元素相同，且前一个元素未被使用（说明是同一层递归的重复选择），则跳过当前元素
4. 使用一个 used 数组标记元素是否被使用过

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void permute2(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& result) {
    // 终止条件：路径长度等于数组长度，找到一个完整排列
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }

    for (int i = 0; i < nums.size(); ++i) {
        // 跳过已使用的元素
        if (used[i]) {
            continue;
        }

        // 去重核心逻辑：同一层递归中，跳过重复元素
        // i > 0 避免越界，nums[i] == nums[i-1] 是重复元素
        // !used[i-1] 说明前一个相同元素未被使用（同一层），跳过当前元素
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) {
            continue;
        }

        // 选择当前元素
        used[i] = true;
        path.push_back(nums[i]);

        // 递归深入下一层
        permute2(nums, used, path, result);

        // 回溯：撤销选择
        path.pop_back();
        used[i] = false;
    }
}

int main() {
    vector<vector<int>> result; // 存储最终结果
    vector<int> path; // 存储当前路径
    vector<bool> used; // 标记元素是否被使用，初始化为 false

    vector<int> nums = {1,2,3};
    used.resize(nums.size(), false); // 初始化标记数组，全部为未使用

    permute2(nums, used, path, result);

    for(vector<int> item : result)
    {
        cout << "[";
        for(int node : item )
        {
            cout << " " << node << " ";
        }
        cout << "]" << endl;
    }

    return 0;
}
        

输出结果

[ 1  2  3 ]
[ 1  3  2 ]
[ 2  1  3 ]
[ 2  3  1 ]
[ 3  1  2 ]
[ 3  2  1 ]
            

二、组合总和 II（LeetCode 40）

问题描述：

• 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
  • candidates 中的每个数字在每个组合中只能使用 一次 。
• 注意：
  • 解集不能包含重复的组合。
• 提示：
  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30
• 示例 1：
  • 输入: candidates = [10,1,2,7,6,1,5], target = 8,
  • 输出:[ [1,1,6], [1,2,5], [1,7], [2,6] ]
• 示例 2：
  • 输入: candidates = [2,5,2,1,2], target = 5,
  • 输出: [ [1,2,2], [5] ]

算法解析：

这道题的关键是去重（数组有重复元素，但组合不能重复）+ 回溯剪枝（元素仅用一次），核心思路：

1. 排序预处理：先对数组排序，让重复元素相邻，为后续去重做准备；
2. 路径选择：从 start 索引开始选取元素，加入当前组合，目标值减去该元素值（元素仅用一次，递归时 start = i+1）；
3. 去重剪枝：同一层递归中，若当前元素和前一个元素相同，且前一个元素未被选取（避免漏解），则跳过当前元素，防止生成重复组合；
4. 终止条件：目标值减到 0 时，当前组合加入结果集；目标值小于 0 时，直接回溯剪枝；
5. 回溯还原：递归返回后，撤销当前选择（从组合中移除最后一个元素）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> res_sum;  // 存储所有合法组合
vector<int> path_sum;         // 存储当前组合路径

// 回溯函数：
// candidates: 排序后的数组
// target: 剩余目标值
// start: 当前遍历起始索引（元素仅用一次，递归传i+1）
void combinationSum2(vector<int>& candidates, int target, int start) {
    // 终止条件1：找到合法组合
    if (target == 0) {
        res_sum.push_back(path_sum);
        return;
    }
    // 终止条件2：剩余目标值 < 0，剪枝
    if (target < 0) {
        return;
    }

    // 遍历当前层的元素（从start开始，避免重复使用元素）
    for (int i = start; i < candidates.size(); ++i) {
        // 核心去重：同一层递归中，跳过重复元素（排序后相邻重复）
        // i > start 保证是同一层的重复，而非同一树枝的重复
        if (i > start && candidates[i] == candidates[i-1]) {
            continue;
        }

        // 选择当前元素
        path_sum.push_back(candidates[i]);
        // 递归：元素仅用一次，起始索引传i+1，剩余目标值减当前元素
        combinationSum2(candidates, target - candidates[i], i + 1);
        // 回溯：撤销选择
        path_sum.pop_back();
    }
}

int main() {
    vector<int> candidates = {10,1,2,7,6,1,5};
    int target = 8;
    // 关键：排序，让重复元素相邻，为去重做准备
    sort(candidates.begin(), candidates.end());
    combinationSum2(candidates, target, 0);
    for(vector<int> item : res_sum)
    {
        cout << "[";
        for(int node : item )
        {
            cout << " " << node << " ";
        }
        cout << "]" << endl;
    }

    return 0;
} 
        

输出结果

[ 1  1  6 ]
[ 1  2  5 ]
[ 1  7 ]
[ 2  6 ]
        

三、电话号码的字母组合（LeetCode 17）

问题描述：

• 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
  • 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

• 提示：
  • 1 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。
• 示例 1：
  • 输入：digits = "23"
  • 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
• 示例 2：
  • 输入：digits = "2"
  • 输出：["a","b","c"]

算法解析：

区间选点问题的最优贪心策略是按区间右端点升序排序，核心逻辑为：每次选择当前未覆盖区间的右端点作为站点，该策略能让单个站点覆盖尽可能多的后续区间，从而保证站点数量最少。

1. 排序：将所有居民区出行区间按右端点 end 升序排列（若右端点相同，按左端点升序，不影响结果）；
2. 初始化：记录已选站点列表（初始为空），标记当前待覆盖的第一个区间；
3. 贪心选点：
   • 取当前第一个未覆盖区间的右端点作为新站点，加入站点列表；
   • 筛选出所有包含该站点的区间（即区间start ≤ 站点 ≤ end），标记为已覆盖；
   • 重复上述操作，直到所有区间均被覆盖。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void letterCombinations(const string& digits, const string mapping[], int index,
               string& path, vector<string>& result) {
    // 终止条件：处理完所有数字，找到一个完整组合
    if (index == digits.size()) {
        result.push_back(path);
        return;
    }

    // 获取当前数字对应的字母串（digits[index] 是字符，减 '0' 转成数字）
    int digit = digits[index] - '0';
    const string& letters = mapping[digit];

    // 遍历当前数字对应的所有字母
    for (char c : letters) {
        // 选择当前字母
        path.push_back(c);
        // 递归处理下一个数字
        letterCombinations(digits, mapping, index + 1, path, result);
        // 回溯：撤销选择
        path.pop_back();
    }
}

int main() {
    vector<string> result; // 存储最终结果
    string path; // 当前拼接的字符串（路径）

    string digits = "23";
    // 数字到字母的映射表（索引对应数字，0/1 无意义）
    const string mapping[] = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };

    letterCombinations(digits, mapping, 0, path, result);

    for(string item : result)
    {
        cout << "[";
        cout << " " << item << " ";
        cout << "]" << endl;
    }

    return 0;
}
        

输出结果

[ ad ]
[ ae ]
[ af ]
[ bd ]
[ be ]
[ bf ]
[ cd ]
[ ce ]
[ cf ]